package com.sheng.leetcode.year2025.month09.day25;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author by ls
 * @date 2025/9/25
 * <p>
 * 120. 三角形最小路径和<p>
 * <p>
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。<p>
 * 每一步只能移动到下一行中相邻的结点上。<p>
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，<p>
 * 如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]<p>
 * 输出：11<p>
 * 解释：如下面简图所示：<p>
 * &nbsp;   2<p>
 * &nbsp; 3 4<p>
 * &nbsp;6 5 7<p>
 * 4 1 8 3<p>
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。<p>
 * <p>
 * 示例 2：<p>
 * 输入：triangle = [[-10]]<p>
 * 输出：-10<p>
 * <p>
 * 提示：<p>
 * 1 <= triangle.length <= 200<p>
 * triangle[0].length == 1<p>
 * triangle[i].length == triangle[i - 1].length + 1<p>
 * -10^4 <= triangle[i][j] <= 10^4<p>
 * <p>
 * 进阶：<p>
 * 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？<p>
 */
public class LeetCode0120 {

    @Test
    public void test() {
        int[][] ints = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
//        int[][] ints = {{-10}};
        //二维数组转换成集合
        List<List<Integer>> triangle = Arrays.stream(ints)
                .map(i -> Arrays.stream(i)
                        .boxed()
                        .collect(Collectors.toList()))
                .collect(Collectors.toList());
        System.out.println(new Solution().minimumTotal(triangle));
    }
}

class Solution {

    private int min = Integer.MAX_VALUE;

    private List<List<Integer>> triangle;

    public int minimumTotal(List<List<Integer>> triangle) {
        // 创建一个 dp[][]
        // 满足 dp[x][y] = triangle.get(x).get(y) + Math.min(dp[x - 1][y], dp[x - 1][y - 1])
        int size = triangle.size();
        int[][] dp = new int[size][size];
        for (int i = 0; i < size; i++) {
            dp[size - 1][i] = triangle.get(size - 1).get(i);
        }
        for (int i = size - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
        // 超时
//        this.triangle = triangle;
//        dfs(0, 0, 0);
//        return min;
    }

    /**
     * 遍历
     *
     * @param row 行数
     * @param col 要选择的列
     * @param sum 金字塔相加的总和
     */
    public void dfs(int row, int col, int sum) {
        if (row == triangle.size()) {
            min = Math.min(min, sum);
            return;
        }
        dfs(row + 1, col, sum + triangle.get(row).get(col));
        dfs(row + 1, col + 1, sum + triangle.get(row).get(col));
    }
}
